package com.formula.datastructure.question.graph;

import com.formula.datastructure.standard.graph.ALEdge;
import com.formula.datastructure.standard.graph.ALVertex;
import com.formula.datastructure.standard.graph.AdjListsGraph;

/*Graph DFS
  1. 访问图的首节点v，标记为已访问
  2. 查找节点v的第一个邻接节点w
  3. 若w存在，执行4, 如果w不存在, 则回到#1, 从v的下一个节点继续
  4. 若w未被访问，对w进行DFS
  5. 查找v的w邻接节点的下一个节点，到第三步
 */
public class GraphDFS {
    int[] visit;

    public GraphDFS(int size) {
        visit = new int[size];
    }

    public void DFS(AdjListsGraph graph, int verIdx) {
        visit[verIdx] = 1;
        visit(graph.vertices[verIdx]);
        ALEdge edge = graph.vertices[verIdx].firstEdge;
        while (edge != null) {
            if (visit[edge.toVerIdx] != 1) {
                DFS(graph, edge.toVerIdx);
            }
            edge = edge.nextEdge;
        }
    }

    private void visit(ALVertex vertex) {
        System.out.println(vertex.data);
    }

    public static void main(String[] args) {
        ALVertex[] vertices = new ALVertex[6];
        ALVertex vertex0 = new ALVertex();
        vertex0.idx = 0;
        vertex0.data = "A";
        ALVertex vertex1 = new ALVertex();
        vertex1.idx = 1;
        vertex1.data = "B";
        ALVertex vertex2 = new ALVertex();
        vertex2.idx = 2;
        vertex2.data = "C";
        ALVertex vertex3 = new ALVertex();
        vertex3.idx = 3;
        vertex3.data = "D";
        ALVertex vertex4 = new ALVertex();
        vertex4.idx = 4;
        vertex4.data = "E";
        ALVertex vertex5 = new ALVertex();
        vertex5.idx = 5;
        vertex5.data = "F";

        ALEdge edgeAB = new ALEdge(1);
        ALEdge edgeAC = new ALEdge(2);
        ALEdge edgeBC = new ALEdge(2);
        ALEdge edgeBD = new ALEdge(3);
        ALEdge edgeCD = new ALEdge(3);
        ALEdge edgeDE = new ALEdge(4);
        ALEdge edgeEF = new ALEdge(5);
        ALEdge edgeFB = new ALEdge(1);
        ALEdge edgeCA = new ALEdge(0);

        vertex0.addEdge(edgeAB);
        vertex0.addEdge(edgeAC);
        vertex1.addEdge(edgeBC);
        vertex1.addEdge(edgeBD);
        vertex2.addEdge(edgeCD);
        vertex3.addEdge(edgeDE);
        vertex4.addEdge(edgeEF);
        vertex5.addEdge(edgeFB);
        vertex2.addEdge(edgeCA);

        vertices[0] = vertex0;
        vertices[1] = vertex1;
        vertices[2] = vertex2;
        vertices[3] = vertex3;
        vertices[4] = vertex4;
        vertices[5] = vertex5;

        AdjListsGraph graph = new AdjListsGraph(vertices);
        GraphDFS search = new GraphDFS(graph.vertices.length);
        search.DFS(graph, 0);
    }
}
